import java.util.*;
import java.io.*;

/**
 * Table generator class builds prediction table.
 * 
 * @author John Mayer
 * @author jamesmini
 *
 */
public class TableGenerator {
	
	/**
	 * Grammar being used.
	 */
    private Grammar gram = new Grammar();
    /**
     * Map to build first set.
     */
    private Map<Symbol,Set<Symbol>> first = new HashMap<Symbol,Set<Symbol>>();
    /**
     * Map to build follow set.
     */
    private Map<Symbol,Set<Symbol>> follow = new HashMap<Symbol,Set<Symbol>>();  
    /**
     * Map to store prediction table.
     */
    private Map<Symbol,Map<Symbol,Set<Rule>>> predTable = 
                 new HashMap<Symbol,Map<Symbol,Set<Rule>>>();      
    
    /**
     * Constructor for TableGenerator
     * @param inFileName File name where grammar is.
     */
    public TableGenerator(String inFileName) {
    	
        readGrammar(inFileName);     
        first();
        follow();
        initializePredTable();
        buildTable();
        
        printFirst();
        printFollow();
        printPredTable();

    }
    
    public Map<Symbol,Map<Symbol,Set<Rule>>> getTable() {
        return predTable;
    }
    
    public Grammar getGrammar() {
        return gram;
    }
    
    private void readGrammar(String inFileName) {
        try {
            Scanner scan = new Scanner(new File(inFileName));
            while(scan.hasNextLine()) {
                Scanner line = new Scanner(scan.nextLine());
                Symbol lhs = new Symbol(line.next());
                if (!line.next().equals("->")) {
                    System.out.println("Grammar file error");
                    System.exit(1);
                }
                List<Symbol> rhs = new ArrayList<Symbol>();
                while(line.hasNext()) {
                    rhs.add(new Symbol(line.next()));
                }
                gram.addRule(new Rule(lhs,rhs));
                
            }
            
        } catch(Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }
    
    /**
     * Compute follow for the grammar.
     */
    private void first() {
    	
    	for(Rule r : gram.rules()) {
    		//Symbol not in first table, so put it there with new set.
    		if(!first.containsKey(r.lhs())){
    			first.put(r.lhs(), new HashSet<Symbol>());
    		}
    		
    		//Add first symbol in LHS to first.
    		first.get(r.lhs()).add(r.rhs().get(0));
    		
    	}
    	
    	//First of all terminals is themselves.
    	for(Symbol s : gram.symbols()) {
    		if(s.isTerm()) {
    			first.put(s, new HashSet<Symbol>());
    			first.get(s).add(s);
    		}
    	}
    	
    	boolean changed_flag = true;
    	
    	while(changed_flag) {
    		changed_flag = false;
    		for(Symbol s_left : first.keySet()) {
    			for(Symbol s_right : first.get(s_left)) {
    				if(s_right.isNonTerm()) {
    					first.get(s_left).remove(s_right);
    					first.get(s_left).addAll(first.get(s_right));
    					changed_flag = true;
    				}
    			}
    		}
    	}
    	
    }
    
    /**
     * Constructs follow table.
     */
    private void follow() {
    	
    	//Put all nonterminals into follow.
    	for(Rule r : gram.rules()) {
    		//Symbol not in first table, so put it there with new set.
    		if(!follow.containsKey(r.lhs())){
    			follow.put(r.lhs(), new HashSet<Symbol>());
    		}
    	}
    	
    	//Add epsilon to follow of start symbol.
    	follow.get(gram.startSymbol()).add(Symbol.EOF);
    	
    	boolean changed_flag = true;
    	
    	//Apply follow rules until changes stop happening.
    	while(changed_flag) {
    		changed_flag = false;
    		for(Rule r : gram.rules()) {
    			//if(r.isNullRule()) {continue;}
    			int rule_size = r.rhs().size();
    			
    			//Rule 1 - A->aBb --- First(b) into Follow(B) when First(b) 
    			if(rule_size > 1 && r.rhs().get(rule_size-2).isNonTerm()) {

    				int pre_size = follow.get(r.rhs().get(rule_size-2)).size();
    				
    				follow.get(r.rhs().get(rule_size-2)).addAll(
    						first.get(r.rhs().get(rule_size-1)));
    				follow.get(r.rhs().get(rule_size-2)).remove(Symbol.EPSILON);
    				
    				if(pre_size != follow.get(r.rhs().get(rule_size-2)).size()) {
    					changed_flag = true;
    				}
    			}
    			//Rule 2 - A->aB --- everything in Follow(A) is in Follow(B)
    			if(r.rhs().get(rule_size-1).isNonTerm()) {
    				int pre_size = follow.get(r.rhs().get(rule_size-1)).size();
    				follow.get(r.rhs().get(rule_size-1)).addAll(
    						follow.get(r.lhs()));
    				if(pre_size != follow.get(r.rhs().get(rule_size-1)).size()) {
    					changed_flag = true;
    				}
    			}
    			//Rule 3 - A->aBb --- If First(b) contains epsilon, everything in
    			//Follow(A) is in Follow(B)
    			if(rule_size > 1 && r.rhs().get(rule_size-2).isNonTerm() &&
    					first.get(r.rhs().get(rule_size-1)).contains(Symbol.EPSILON)) {
    				int pre_size = follow.get(r.rhs().get(rule_size-2)).size();
    				follow.get(r.rhs().get(rule_size-2)).addAll(
    						follow.get(r.lhs()));
    				if(pre_size != follow.get(r.rhs().get(rule_size-2)).size()) {
    					changed_flag = true;
    				}
    			}
    			
    		}
    	}
    	
    }
    
    /**
     * Builds lookup table from first and follow tables
     */
    private void buildTable() {
    	for(Rule r : gram.rules()) {
    		for(Symbol a : first.get(r.lhs())) {
    			if(!a.equals(Symbol.EPSILON) && !a.equals(Symbol.EOF)) {
    				if(r.rhs().get(0).isTerm()){
    					
    					predTable.get(r.lhs()).get(r.rhs().get(0)).clear();
    					predTable.get(r.lhs()).get(r.rhs().get(0)).add(r);
    					
    				}
    				
    				
    				if(predTable.get(r.lhs()).get(a).isEmpty()) {
    					predTable.get(r.lhs()).get(a).add(r);
    				}
    			}
    			
    		}
    		if(r.isNullRule()) {
    			for(Symbol b : follow.get(r.lhs())) {
    				if(predTable.get(r.lhs()).get(b).isEmpty()){
    					predTable.get(r.lhs()).get(b).add(r);
    				}
    			}
    			if(follow.get(r.lhs()).contains(Symbol.EOF)) {
    				if(predTable.get(r.lhs()).get(Symbol.EOF).isEmpty()){
    					predTable.get(r.lhs()).get(Symbol.EOF).add(r);
    				}
    			}
    		}
    	}
    	
    }
    
    /**
     * Initializes predTable
     */
    private void initializePredTable() {
    	Set<Symbol> terms = new HashSet<Symbol>();
    	
    	for(Symbol s : gram.symbols()) {
    		if(s.isTerm() && !s.equals(Symbol.EPSILON)) {
    			terms.add(s);
    		}
    	}
    	
    	terms.add(Symbol.EOF);
    	
    	for(Rule r : gram.rules()) {
    		//Symbol not in table, so put it there with new set.
    		if(!predTable.containsKey(r.lhs())){
    			predTable.put(r.lhs(), new HashMap<Symbol, Set<Rule>>());
    		}
    		for(Symbol s : terms) {
    			
    			if(!predTable.get(r.lhs()).containsKey(s)) {
    				predTable.get(r.lhs()).put(s, new HashSet<Rule>());
    			}
    					
    		}
    	 		
    	}
    }
    
    /**
     * Print the results of first.
     */
    private void printFirst() {
        System.out.println("Results of First:");
    	for(Symbol s : first.keySet()) {
        	System.out.print(s.toString() + ": [");
        	for(Symbol t : first.get(s)) {
        		System.out.print(t + " ");
        	}
        	System.out.println("]");
        }
        System.out.println();
    }
    
    /**
     * Prints the results of follow.
     */
    private void printFollow() {
        System.out.println("Results of Follow:");
    	for(Symbol s : follow.keySet()) {
        	System.out.print(s.toString() + ": [");
        	for(Symbol t : follow.get(s)) {
        		System.out.print(t + " ");
        	}
        	System.out.println("]");
        }
        System.out.println();
    }
    
    /**
     * Prints parse table
     */
    private void printPredTable() {
    	Set<Symbol> terms = new HashSet<Symbol>();
    	
    	for(Symbol s : gram.symbols()) {
    		if(s.isTerm() && !s.equals(Symbol.EPSILON)) {
    			terms.add(s);
    		}
    	}
    	
    	terms.add(Symbol.EOF);
    	
    	Set<Symbol> non_term = predTable.keySet();
    	System.out.println("Transition Table");
    	for(Symbol s : non_term) {
    		System.out.println("Stack = " + s.toString());
    		for(Symbol t : terms) {
    			System.out.println(
    					"\t"+t.toString()+" : "+predTable.get(s).get(t).toString());
    			
    		}
    	}
    }
}